#pragma once
#include "yzrutil.h"
#include "collection/Deque.hpp"
#include "lang/Exception.h"
#include "lang/System.h"
#include "util/Util.h"
#include "array/Array.hpp"
#include "array/Arrays.h"
#include <functional>
#include <initializer_list>
#include <optional>
#include <memory>

namespace yzrilyzr_collection{
	template<typename E>
	ECLASS(ArrayDeque, public Deque<E>){
	private:
	static constexpr u_index DEFAULT_CAPACITY=16;

	// 使用std::optional来区分空槽位和存储的值
	std::shared_ptr<yzrilyzr_array::Array<std::optional<E>>> elements=nullptr;
	u_index head=0;
	u_index tail=0;
	u_index modCount=0;

	// Circular increment
	u_index inc(u_index i, u_index modulus) const{
		return (i + 1) % modulus;
	}

	// Circular decrement
	u_index dec(u_index i, u_index modulus) const{
		return (i == 0)?modulus - 1:i - 1;
	}

	// Circular distance
	u_index sub(u_index i, u_index j, u_index modulus) const{
		return (i >= j)?i - j:modulus - (j - i);
	}

	void grow(u_index needed){
		this->modCount++;
		u_index oldCapacity=elements->length;
		u_index newCapacity;

		// Double capacity if small; else grow by 50%
		u_index jump=(oldCapacity < 64)?(oldCapacity + 2):(oldCapacity >> 1);

		// Handle overflow conditions like Java version
		u_index minCapacity=oldCapacity + needed;
		if(jump < needed || (newCapacity=oldCapacity + jump) > std::numeric_limits<u_index>::max() - 8){
			newCapacity=newCapacityF(needed, jump);
		} else{
			newCapacity=oldCapacity + jump;
		}

		// Use Arrays::copyOf to create new array
		auto newElements=yzrilyzr_array::Arrays::copyOf(*elements, newCapacity);

		// Exceptionally, here tail == head needs to be disambiguated
		if(tail < head || (tail == head && (*elements)[head].has_value())){
			// wrap around; slide first leg forward to end of array
			u_index newSpace=newCapacity - oldCapacity;

			// Copy elements from head to end of old array to new position
			yzrilyzr_lang::System::arraycopy(*newElements, head,
											 *newElements, head + newSpace,
											 oldCapacity - head);

			 // Clear the original positions
			for(u_index i=head, to=head + newSpace; i < to; i++){
				(*newElements)[i]=std::nullopt;
			}

			head+=newSpace;
		}

		elements=newElements;
	}
	u_index newCapacityF(u_index needed, u_index jump){
		u_index oldCapacity=elements->length;
		u_index minCapacity;

		if((minCapacity=oldCapacity + needed) > std::numeric_limits<u_index>::max() - 8){
			if(minCapacity < 0){ // overflow
				throw yzrilyzr_lang::IllegalStateException("Sorry, deque too big");
			}
			return std::numeric_limits<u_index>::max();
		}

		if(needed > jump){
			return minCapacity;
		}

		return (oldCapacity + jump > std::numeric_limits<u_index>::max() - 8)
			?std::numeric_limits<u_index>::max()
			:oldCapacity + jump;
	}
	bool deleteElement(u_index i){
		u_index capacity=elements->length;
		u_index h=head;
		u_index t=tail;

		// number of elements before to-be-deleted element
		u_index front=sub(i, h, capacity);
		// number of elements after to-be-deleted element
		u_index back=sub(t, i, capacity) - 1;

		if(front < back){
			// move front elements forwards
			if(h <= i){
				yzrilyzr_lang::System::arraycopy(*elements, h, *elements, h + 1, front);
			} else{
				// Wrap around
				yzrilyzr_lang::System::arraycopy(*elements, 0, *elements, 1, i);
				(*elements)[0]=(*elements)[capacity - 1];
				yzrilyzr_lang::System::arraycopy(*elements, h, *elements, h + 1, front - (i + 1));
			}
			(*elements)[h]=std::nullopt;
			head=inc(h, capacity);
			return false;
		} else{
			// move back elements backwards
			tail=dec(t, capacity);
			if(i <= tail){
				yzrilyzr_lang::System::arraycopy(*elements, i + 1, *elements, i, back);
			} else{
				// Wrap around
				yzrilyzr_lang::System::arraycopy(*elements, i + 1, *elements, i, capacity - (i + 1));
				(*elements)[capacity - 1]=(*elements)[0];
				yzrilyzr_lang::System::arraycopy(*elements, 1, *elements, 0, t - 1);
			}
			(*elements)[tail]=std::nullopt;
			return true;
		}
	}

	void circularClear(u_index start, u_index end){
		u_index capacity=elements->length;
		for(u_index i=start; i != end; i=inc(i, capacity)){
			(*elements)[i]=std::nullopt;
		}
	}

	public:
	ArrayDeque() : ArrayDeque(DEFAULT_CAPACITY){}

	~ArrayDeque(){}

	explicit ArrayDeque(u_index numElements){
		u_index initialCapacity=(numElements < 1)?1:
			(numElements == std::numeric_limits<u_index>::max())?
			std::numeric_limits<u_index>::max():numElements + 1;
		elements=std::make_shared<yzrilyzr_array::Array<std::optional<E>>>(initialCapacity);
		head=0;
		tail=0;
	}

	ArrayDeque(const std::initializer_list<E>&init) : ArrayDeque(init.size()){
		for(const auto & item : init){
			addLast(item);
		}
	}

	ArrayDeque(const Collection<E>&c) : ArrayDeque(c.size()){
		addAll(c);
	}

	// Deque methods
	void addFirst(const E & e) override{
		modCount++;
		u_index capacity=elements->length;
		head=dec(head, capacity);
		(*elements)[head]=e;
		if(head == tail){
			grow(1);
		}
	}

	void addLast(const E & e) override{
		modCount++;
		(*elements)[tail]=e;
		tail=inc(tail, elements->length);
		if(head == tail){
			grow(1);
		}
	}

	bool offerFirst(const E & e) override{
		try{
			addFirst(e);
			return true;
		} catch(...){
			return false;
		}
	}

	bool offerLast(const E & e) override{
		try{
			addLast(e);
			return true;
		} catch(...){
			return false;
		}
	}

	E removeFirst() override{
		std::optional<E> e=pollFirst();
		if(!e.has_value()){
			throw yzrilyzr_lang::NoSuchElementException();
		}
		return e.value();
	}

	E removeLast() override{
		std::optional<E> e=pollLast();
		if(!e.has_value()){
			throw yzrilyzr_lang::NoSuchElementException();
		}
		return e.value();
	}

	std::optional<E> pollFirst() noexcept override{
		if(isEmpty()){
			return std::nullopt;
		}

		u_index h=head;
		std::optional<E> e=(*elements)[h];
		if(!e.has_value()){
			return std::nullopt; // 这不应该发生
		}
		(*elements)[h]=std::nullopt;
		head=inc(h, elements->length);
		modCount++;
		return e;
	}

	std::optional<E> pollLast() noexcept override{
		if(isEmpty()){
			return std::nullopt;
		}

		u_index t=dec(tail, elements->length);
		std::optional<E> e=(*elements)[t];
		if(!e.has_value()){
			return std::nullopt; // 这不应该发生
		}
		(*elements)[t]=std::nullopt;
		tail=t;
		modCount++;
		return e;
	}

	E getFirst() const override{
		std::optional<E> e=peekFirst();
		if(!e.has_value()){
			throw yzrilyzr_lang::NoSuchElementException();
		}
		return e.value();
	}

	E getLast() const override{
		std::optional<E> e=peekLast();
		if(!e.has_value()){
			throw yzrilyzr_lang::NoSuchElementException();
		}
		return e.value();
	}

	std::optional<E> peekFirst() const noexcept override{
		if(isEmpty()){
			return std::nullopt;
		}
		return (*elements)[head];
	}

	std::optional<E> peekLast() const noexcept override{
		if(isEmpty()){
			return std::nullopt;
		}
		u_index t=dec(tail, elements->length);
		return (*elements)[t];
	}

	bool removeFirstOccurrence(const E & o) override{
		if(isEmpty()){
			return false;
		}

		u_index capacity=elements->length;
		u_index i=head;
		u_index end=tail;

		while(i != end){
			auto & elem=(*elements)[i];
			if(elem.has_value() && elem.value() == o){
				deleteElement(i);
				return true;
			}
			i=inc(i, capacity);
		}
		return false;
	}

	bool removeLastOccurrence(const E & o) override{
		if(isEmpty()){
			return false;
		}

		u_index capacity=elements->length;
		u_index i=dec(tail, capacity);
		u_index end=head;

		while(true){
			auto & elem=(*elements)[i];
			if(elem.has_value() && elem.value() == o){
				deleteElement(i);
				return true;
			}
			if(i == end){
				break;
			}
			i=dec(i, capacity);
		}

		return false;
	}

	// Queue methods
	bool offer(const E & e) override{
		return offerLast(e);
	}

	std::optional<E> poll() noexcept override{
		return pollFirst();
	}

	std::optional<E> peek() const noexcept override{
		return peekFirst();
	}

	// Stack methods
	void push(const E & e) override{
		addFirst(e);
	}

	E pop() override{
		return removeFirst();
	}

	// Collection methods
	u_index size() const override{
		return sub(tail, head, elements->length);
	}

	bool isEmpty() const override{
		return head == tail;
	}

	bool contains(const E & o) const override{
		if(isEmpty()){
			return false;
		}

		u_index capacity=elements->length;
		u_index i=head;
		u_index end=tail;

		while(i != end){
			auto & elem=(*elements)[i];
			if(elem.has_value() && elem.value() == o){
				return true;
			}
			i=inc(i, capacity);
		}
		return false;
	}

	bool remove(const E & o) override{
		return removeFirstOccurrence(o);
	}

	void clear() override{
		modCount++;
		if(!isEmpty()){
			circularClear(head, tail);
		}
		head=0;
		tail=0;
	}

	bool add(const E & e) override{
		return Queue<E>::add(e);
	}

	E remove() override{
		return Queue<E>::remove();
	}

	E element() const override{
		return Queue<E>::element();
	}

	std::shared_ptr<yzrilyzr_array::Array<E>> toArray()const override{
		auto result=std::make_shared<yzrilyzr_array::Array<E>>(size());

		u_index currentSize=size();
		if(currentSize == 0){
			return result;
		}

		u_index index=0;
		u_index capacity=elements->length;
		u_index i=head;
		u_index end=tail;

		while(i != end){
			auto & elem=(*elements)[i];
			if(elem.has_value()){
				(*result)[index++]=elem.value();
			}
			i=inc(i, capacity);
		}

		return result;
	}

	bool addAll(const Collection<E>&c) override{
		if(&c == this){
			throw yzrilyzr_lang::IllegalArgumentException();
		}

		auto a=c.toArray();
		u_index numNew=a->length;
		if(numNew == 0){
			return false;
		}

		modCount++;
		u_index currentSize=size();
		if(numNew > elements->length - currentSize - 1){
			grow(numNew);
		}

		// Add all elements to the end
		for(u_index i=0; i < numNew; i++){
			(*elements)[tail]=(*a)[i];
			tail=inc(tail, elements->length);
			if(head == tail){
				// Should not happen due to grow, but just in case
				grow(1);
			}
		}

		return true;
	}

	// Iterator
	ECLASS(ArrayDequeIterator, public Iterator<E>){
	private:
	u_index cursor;
	u_index remaining;
	u_index lastRet=std::numeric_limits<u_index>::max();
	u_index expectedModCount;
	const ArrayDeque * cdeque=nullptr;
	ArrayDeque * deque=nullptr;

	void checkForComodification(){
		if(cdeque->modCount != expectedModCount){
			throw yzrilyzr_lang::ConcurrentModificationException();
		}
	}

	public:
	ArrayDequeIterator(const ArrayDeque * cdeque, ArrayDeque * deque)
		: cdeque(cdeque), deque(deque), expectedModCount(cdeque->modCount),
		cursor(cdeque->head), remaining(cdeque->size()){}

	bool hasNext() const override{
		return remaining > 0;
	}

	E & next() override{
		checkForComodification();
		if(remaining <= 0){
			throw yzrilyzr_lang::NoSuchElementException();
		}

		auto & elem=(*cdeque->elements)[cursor];
		if(!elem.has_value()){
			throw yzrilyzr_lang::ConcurrentModificationException();
		}

		E & e=elem.value();
		lastRet=cursor;
		cursor=cdeque->inc(cursor, cdeque->elements->length);
		remaining--;
		return e;
	}

	void remove() override{
		if(lastRet == std::numeric_limits<u_index>::max()){
			throw yzrilyzr_lang::IllegalStateException();
		}
		checkForComodification();
		if(deque != nullptr){
			deque->deleteElement(lastRet);
			expectedModCount=cdeque->modCount;
		}
		lastRet=std::numeric_limits<u_index>::max();
	}
	};

	std::unique_ptr<Iterator<E>> iterator() override{
		return std::make_unique<ArrayDequeIterator>(this, this);
	}

	std::unique_ptr<Iterator<E>> constIterator() const override{
		return std::make_unique<ArrayDequeIterator>(this, nullptr);
	}

	// Descending iterator
	ECLASS(DescendingArrayDequeIterator, public Iterator<E>){
	private:
	u_index cursor;
	u_index remaining;
	u_index lastRet=std::numeric_limits<u_index>::max();
	u_index expectedModCount;
	const ArrayDeque * cdeque=nullptr;
	ArrayDeque * deque=nullptr;

	void checkForComodification(){
		if(cdeque->modCount != expectedModCount){
			throw yzrilyzr_lang::ConcurrentModificationException();
		}
	}

	public:
	DescendingArrayDequeIterator(const ArrayDeque * cdeque, ArrayDeque * deque)
		: cdeque(cdeque), deque(deque), expectedModCount(cdeque->modCount),
		cursor(cdeque->dec(cdeque->tail, cdeque->elements->length)),
		remaining(cdeque->size()){}

	bool hasNext() const override{
		return remaining > 0;
	}

	E & next() override{
		checkForComodification();
		if(remaining <= 0){
			throw yzrilyzr_lang::NoSuchElementException();
		}

		auto & elem=(*cdeque->elements)[cursor];
		if(!elem.has_value()){
			throw yzrilyzr_lang::ConcurrentModificationException();
		}

		E & e=elem.value();
		lastRet=cursor;
		cursor=cdeque->dec(cursor, cdeque->elements->length);
		remaining--;
		return e;
	}

	void remove() override{
		if(lastRet == std::numeric_limits<u_index>::max()){
			throw yzrilyzr_lang::IllegalStateException();
		}
		checkForComodification();
		if(deque != nullptr){
			deque->deleteElement(lastRet);
			expectedModCount=cdeque->modCount;
		}
		lastRet=std::numeric_limits<u_index>::max();
	}
	};

	std::unique_ptr<Iterator<E>> descendingIterator() override{
		return std::make_unique<DescendingArrayDequeIterator>(this, this);
	}
	};
}